Computer-based graphical processing systems and methods are widely used for displaying three-dimensional images on a two-dimensional graphical display. The three-dimensional images are typically formed of collections of polygons. In order to add surface details to the image, texture mapping is typically used. In texture mapping, a patterned image or texture bitmap is plastered onto a polygon surface to thereby produce a modified object with the added detail of the texture. When the texture-mapped polygon is rendered into a scene, the texture is also rendered as if it were painted on the polygon.
Texture mapping of a polygon on a graphical display is generally accomplished by finding texture coordinates at the center of each pixel inside the polygon and coloring the pixels with the corresponding bits from the texture. The bits from the texture are also referred to as "texels".
Texture mapping allows detail to be added to a scene without significantly complicating the scene's model. For example, brick walls, tiled and carpeted floors, and complex control panels may be rendered with just a few polygons. Pictures on walls can be digitized versions of actual pictures. Grass, trees, water and bushes may be rendered convincingly with minimal modeling. Thus, with texture mapping, a model-maker can create more realistic models with less effort.
Although texture mapping simplifies modeling, it complicates rendering of the scene on the two-dimensional graphical display. If the textures are not rendered precisely, the viewer may see annoying distortion. Generally, precise perspective correct texture mapping may be provided, but at the expense of rendering speed.
There are several texture mapping methods and systems currently in use. Some sacrifice precision for the sake of speed, as is often necessary when developing interactive systems. Others are precise, but are too slow for interactive use.
The simplest high speed texture mapping system and method is linear approximation. For example, a polygon with correct texture points at the vertices is scan-converted from top-to-bottom, linearly interpolating texture coordinates both along polygon edges and across scanlines. Linear approximation is not exact, however, because texture coordinates are linear with respect to pre-perspective projection world space, not post-projection display space.
For example, consider a segment in screen space from (x.sub.s1, y.sub.s1) to (x.sub.s2, y.sub.s2), with correct texture coordinates (u.sub.1, v.sub.1) and (u.sub.2, v.sub.2). To linearly interpolate texture coordinates at (x.sub.s, y.sub.s) along the segment: EQU u.sub.linearapprox =u.sub.1 +q (u.sub.2 -u.sub.1) EQU v.sub.linearapprox =v.sub.1 +q (u.sub.2 -u.sub.1) (1)
where q=(x.sub.s -x.sub.s1)/(x.sub.s2 -x.sub.s1) or PA1 where q is as described in Equations (1). PA1 where w is interpolated between (x.sub.s1, y.sub.s1) and (x.sub.s2, y.sub.s2), i.e.: EQU w=w.sub.1 +q(w.sub.2 -w.sub.1) PA1 where q=(x.sub.s -x.sub.s1)/(x.sub.s2 -x.sub.s1) or PA1 (x.sub.s1, y.sub.s1) to (x.sub.s2, y.sub.s2) PA1 and where w.sub.1 =1/z.sub.1 and w.sub.2 =1/z.sub.2 PA1 u.sub.correct =u.sub.1 +r(u.sub.2 -u.sub.1) PA1 r=(x-x.sub.1)/(x.sub.2 -x.sub.1) PA1 x=(x.sub.s /w) PA1 w=w.sub.1 +q(w.sub.2 -w.sub.1) PA1 q=(x.sub.s -x.sub.s1)/(x.sub.s2 -x1.sub.s1) PA1 w.sub.1 =1/z.sub.1 PA1 w.sub.2 =1/z.sub.2 PA1 w.sub.1 =1/z.sub.1 PA1 w.sub.2 =1/z.sub.2.
(y.sub.s -y.sub.s1)/(y.sub.s2 -y.sub.s1) PA2 (y.sub.2 -y.sub.s1)/(y.sub.s2 -y.sub.s1)
that is, q is the fraction of the distance along the segment from (x.sub.s1, y.sub.s1) to (x.sub.s2, y.sub.s2). The domain of the u and v variables depends on the size of the texture bitmap. To simplify the equations, the texture coordinates are normalized so that u.sub.1 =v.sub.1 =0, and u.sub.2 =v.sub.2 =1: EQU u.sub.linearapprox =q EQU v.sub.linearapprox =q (2)
A system or method can calculate delta values for u and v, and can add to calculate each successive texture coordinate along the line. To perform a complete two-dimensional texture mapping as described above, Equations (2) are used to interpolate texture coordinates both along polygon edges and across scanlines.
Linear approximation is relatively simple and computationally inexpensive, but the distortion it produces is usually unacceptable. As an example, see FIG. 1 which illustrates a cube which is texture-mapped with a checkerboard pattern. The lines separating the rows and columns of squares should be straight, but they are bent and twisted, especially on the top and right sides of the cube.
Approximation can be improved by using quadratic rather than linear interpolation. See the publications by D. Kirk et al., "The Rendering Architecture of the DN10000VS", Proceedings of SIGGRAPH '90, Dallas, Tex., Aug. 6-10, 1990, pages 304-305, and G. Wolberg, "Digital Image Warping", IEEE Computer Society Press, Los Alamitos, Calif., 1990, pages 199-200. For a modest increase in per-pixel calculation, texture mapped surfaces can cover a wider range of depth and still be rendered without noticeable distortion. Distortion still occurs, however, and in certain circumstances this distortion looks worse than distortion from linear approximation.
A second basic strategy for perspective correct texture mapping is subdivision. A polygon is divided, typically in half, to produce subpolygons, and correct texture coordinates are computed exactly for the new subpolygon corners. Each subpolygon is further subdivided, typically in half, and at some point the resulting subpolygons are rendered using linear, quadratic, or even constant approximation. An example of subdivision is described in Japanese published Patent Application 06-036039, published Feb. 10, 1994 to Takahisa et al. entitled Texture Mapping Device. As shown therein, a texture mapping device is equipped with an error evaluation expression calculation part, which calculates an error evaluation expression. When the maximum value of the error evaluation expression exceeds a predetermined permissible error, the projection plane is subdivided.
Another example of subdivision is described in U.S. Pat. No. 5,307,450 to Grossman entitled Z-Subdivision for Improved Texture Mapping. Disclosed is a graphical display system and method for Z-subdivision of polygons into quadrilaterals and triangles whose vertices are arranged between two adjacent Z-planes. Once a primitive is sliced into component portions, a texture is mapped onto each component portion by interpolating texture parameters to points on or within the component portion.
There are occasions where texture mapping must be exact, even if a viewer cannot see gross distortion. For example, consider a polygon with a city map texture. There may be situations where a rendering system places "pins" on the map to mark locations, and renders the pins as additional polygons. If the texture mapping is not sufficiently accurate, the pins will likely be over incorrect positions on the map even though the map may not look distorted. An even worse problem is that the map will "dance" around beneath the pins as the observer moves.
Exact calculation systems and methods often calculate the correct texture coordinates incrementally so that a texture-mapped polygon may be rendered by incrementing along polygon edges and across scanlines, just as in the linear approximation algorithms described above. See a publication by G. Wolberg, entitled "Digital Image Warping", IEEE Computer Society Press, Los Alamitos, Calif., 1990, page 196.
For example, assuming a line in pre-perspective projection space is rotated and translated so that the viewing vector is along the z axis, projecting the line's endpoints (x.sub.1, y.sub.1, z.sub.1) and (x.sub.2, y.sub.2, z.sub.2) requires dividing the non-depth coordinates by the depth: EQU (x.sub.s1, y.sub.s1)=(x.sub.1 /z.sub.1, y.sub.1 /z.sub.1) EQU (x.sub.s2, y.sub.s2)=(x.sub.2 /z.sub.2, y.sub.2 /z.sub.2)
Although the texture coordinates are not linear in screen space, the depth reciprocal, 1/z, is linear. See the textbook entitled Computer Graphics Principles and Practice, Second Edition by J. Foley et al., Addison-Wesley Publishing Company, Inc., 1990, pages 230-237. Accordingly, for a screen point (x.sub.s, y.sub.s) along the line: EQU (x, y, z)=(x.sub.s /w, y.sub.s /w, 1/w)
that is, q is the fraction of the distance along the segment from
In order to obtain a correct texture coordinate for screen coordinate (x.sub.s, y.sub.s), the exact calculation technique inverse projects to find the world coordinates (x, y) and uses these coordinates to linearly interpolate the texture coordinates:
These equations can also use y.sub.s values instead of x.sub.s values, and there is a similar operation to find v coordinates. Normalizing u, and substituting r into the equation for u.sub.correct : EQU u.sub.correct =(x-x.sub.1)/(x.sub.2 -x.sub.1)
Substituting in x=x.sub.s /w, x.sub.1 =x.sub.s1 /w.sub.1, and x.sub.2 =x.sub.s2 /w.sub.2 : ##EQU1## w=w.sub.1 +q(w.sub.2 -w.sub.1) q=(x.sub.s -x.sub.s1)/(x.sub.s2 -x.sub.s1)
In order to obtain correct texture points along the line ((x.sub.1, y.sub.1), (x.sub.2, y.sub.2)), rendering increments x.sub.s from x.sub.1 to x.sub.2 and w from w.sub.1 to w.sub.2 and evaluates Equation (3) at each increment. An entire polygon can thus be rendered in this manner, using Equation (3) to incrementally calculate correct texture coordinates along polygon edges and also across scanlines.
Unfortunately, exact calculation requires at least two divides (or a divide and two multiplies) per pixel. Although perspective correct results are obtained, the calculation time is generally excessive.
In conclusion, texture mapping methods and systems have generally been either accurate and slow or fast and inaccurate. As high resolution graphical display systems are increasingly being used for many consumer, commercial and military applications, there is a greater need for perspective correct texture mapping. Moreover, as the systems are increasingly used for real-time viewing of three-dimensional scenes, there is an increased need for high speed texture mapping. Even as machines become faster, screen resolutions and polygon counts will continue to increase, so that fast, perspective correct texture mapping will continue to be needed.